package tree.递归.剑指;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N剑指offer二叉树的最近公共祖先II58.java
 * @Description TODO https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
 * @createTime 2021年03月29日 22:08:00
 */
public class N剑指offer二叉树的最近公共祖先II58 {
    /**
     * p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
     * p = root p=root ，且 qq 在 root root 的左或右子树中；
     * q = root q=root ，且 pp 在 root root 的左或右子树中；
     *
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		//如果root为空，说明左右子树都不包含
        if (root==null||root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //当 leftleft 和 rightright 同时为空 ：说明 rootroot 的左 / 右子树中都不包含 p,qp,q ，返回 nullnull
        if (left == null && right == null) {
            return null;
        }
        if (left==null){
            return right;
        }
        if (right==null){
            return left;
        }
        return root;
    }
}
